package 纯数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class No119杨辉三角II {

    /**
     * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *
     * 示例:
     * 输入: 3
     * 输出: [1,3,3,1]
     * 进阶：
     * 你可以优化你的算法到 O(k) 空间复杂度吗？
     */

    //LeetCode有更好的公式法,小白就略过了
    public List<Integer> getRow(int rowIndex) {

        rowIndex+=1;

        List<List<Integer>> lists=new ArrayList<>(rowIndex);

        List<Integer> baseOne=new ArrayList<>();
        baseOne.add(1);
        lists.add(baseOne);

        for (int i = 1; i < rowIndex; i++) {

            List<Integer> list=new ArrayList<>();
            //n 拿上一行的 [n-1]+[n]
            for (int j = 0; j <= i; j++) {

                int one = 0;
                if(j>0) {
                    one = lists.get(i - 1).get(j - 1);
                }
                int two = 0;
                if(j<i) {
                    two = lists.get(i - 1).get(j);
                }
                list.add(one+two);
            }
            lists.add(list);
        }

        return lists.get(rowIndex-1);
    }

}
